<!DOCTYPE html>
<html>
<head>
    

    

    



    <meta charset="utf-8">
    
    
    
    
    <title>MySQL中的索引为什么使用B+树实现 | 博客主页 | 世界是个球，前方总有路！</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="MySQL">
    <meta name="description" content="一、前言&amp;emsp;&amp;emsp;这几天在研究MySQL相关的内容，而MySQL中比较重要的一个内容就是索引。对MySQL索引有了解的应该都知道，B+树是MySQL索引实现的一个主要的数据结构。今天这篇博客就来简单介绍一下B树、B+树以及MySQL索引使用这种数据结构实现的原因。   二、正文2.1 B树&amp;emsp;&amp;emsp;关于B树的操作细节我这里就不详细介绍了，这里主要介绍一下B树的结构，让大">
<meta property="og:type" content="article">
<meta property="og:title" content="MySQL中的索引为什么使用B+树实现">
<meta property="og:url" content="http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/index.html">
<meta property="og:site_name" content="博客主页">
<meta property="og:description" content="一、前言&amp;emsp;&amp;emsp;这几天在研究MySQL相关的内容，而MySQL中比较重要的一个内容就是索引。对MySQL索引有了解的应该都知道，B+树是MySQL索引实现的一个主要的数据结构。今天这篇博客就来简单介绍一下B树、B+树以及MySQL索引使用这种数据结构实现的原因。   二、正文2.1 B树&amp;emsp;&amp;emsp;关于B树的操作细节我这里就不详细介绍了，这里主要介绍一下B树的结构，让大">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/1.png">
<meta property="og:image" content="http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/2.png">
<meta property="article:published_time" content="2020-04-04T15:27:50.000Z">
<meta property="article:modified_time" content="2020-04-04T19:32:07.869Z">
<meta property="article:author" content="特务依昂">
<meta property="article:tag" content="MySQL">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/1.png">
    
        <link rel="alternate" type="application/atom+xml" title="博客主页" href="/blog/atom.xml">
    
    <link rel="shortcut icon" href="/blog/img/title.png">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/blog/img/brand.jpg)">
      <div class="brand">
        <a href="/blog/" class="avatar waves-effect waves-circle waves-light">
          <img src="/blog/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">特务依昂</h5>
          <a href="mailto:1131564805@qq.com" title="1131564805@qq.com" class="mail">1131564805@qq.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/blog/"  >
                <i class="icon icon-lg icon-home"></i>
                主页
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                博客
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                标签
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/blog/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                分类
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/tewuyiang" target="_blank" >
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://weibo.com/u/5516635708/" target="_blank" >
                <i class="icon icon-lg icon-weibo"></i>
                Weibo
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://www.cnblogs.com/tuyang1129/" target="_blank" >
                <i class="icon icon-lg icon-link"></i>
                博客园
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">MySQL中的索引为什么使用B+树实现</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">MySQL中的索引为什么使用B+树实现</h1>
        <h5 class="subtitle">
            
                <time datetime="2020-04-04T15:27:50.000Z" itemprop="datePublished" class="page-time">
  2020-04-04
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/blog/categories/MySQL/">MySQL</a></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#一、前言"><span class="post-toc-number">1.</span> <span class="post-toc-text">一、前言</span></a></li><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#二、正文"><span class="post-toc-number">2.</span> <span class="post-toc-text">二、正文</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-1-B树"><span class="post-toc-number">2.1.</span> <span class="post-toc-text">2.1 B树</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-2-为什么需要B树"><span class="post-toc-number">2.2.</span> <span class="post-toc-text">2.2 为什么需要B树?</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-3-B树存在的问题"><span class="post-toc-number">2.3.</span> <span class="post-toc-text">2.3 B树存在的问题</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-4-B-树"><span class="post-toc-number">2.4.</span> <span class="post-toc-text">2.4 B+树</span></a></li><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#2-5-InnoDB和MyISAM中索引的实现"><span class="post-toc-number">2.5.</span> <span class="post-toc-text">2.5 InnoDB和MyISAM中索引的实现</span></a></li></ol></li><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#三、总结"><span class="post-toc-number">3.</span> <span class="post-toc-text">三、总结</span></a></li><li class="post-toc-item post-toc-level-1"><a class="post-toc-link" href="#四、参考"><span class="post-toc-number">4.</span> <span class="post-toc-text">四、参考</span></a></li></ol>
        </nav>
    </aside>


<article id="post-浅析B树、B-树以及MySQL中的使用"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">MySQL中的索引为什么使用B+树实现</h1>
        <div class="post-meta">
            <time class="post-time" title="2020-04-04 23:27:50" datetime="2020-04-04T15:27:50.000Z"  itemprop="datePublished">2020-04-04</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/blog/categories/MySQL/">MySQL</a></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style='display:none'>
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h1 id="一、前言"><a href="#一、前言" class="headerlink" title="一、前言"></a>一、前言</h1><p>&emsp;&emsp;这几天在研究<code>MySQL</code>相关的内容，而<code>MySQL</code>中比较重要的一个内容就是索引。对<code>MySQL</code>索引有了解的应该都知道，B+树是<code>MySQL</code>索引实现的一个主要的数据结构。今天这篇博客就来简单介绍一下B树、B+树以及<code>MySQL</code>索引使用这种数据结构实现的原因。</p>
<br>

<h1 id="二、正文"><a href="#二、正文" class="headerlink" title="二、正文"></a>二、正文</h1><h2 id="2-1-B树"><a href="#2-1-B树" class="headerlink" title="2.1 B树"></a>2.1 B树</h2><p>&emsp;&emsp;关于B树的操作细节我这里就不详细介绍了，这里主要介绍一下B树的结构，让大家对B树有一个大致的了解。</p>
<blockquote>
<p>&emsp;&emsp;这里首先要纠正一个问题，网上大量文章将B树称为B-（减）树，但其实这是一种错误的叫法。会这么叫是因为B树的英文名称为“B-Tree”，错误的翻译导致这种错误的叫法逐渐传开。但实际上这里的“-”是<strong>杠</strong>，而不是<strong>减</strong>，由于存在B+树，所以大家都觉得存在一个B-（减）树是很正常的，但实际上，B+树的英文完整写法应该是B+-Tree，“+”是加，但“-”是杠。除此之外，甚至有人认为B树就是二叉搜索树（Binary Search Tree，简称BST），这就错的更加离谱了。</p>
</blockquote>
<p>&emsp;&emsp;B树是一棵多路平衡查找树，相信很多人都了解过二叉搜索树，而B树和二叉搜索树类似，只是B树的每一个节点可以有超过两个子节点。而B树中，每一个节点具体可以有几个子节点，这与这棵B树的<strong>阶</strong>有关，而树的阶一般用字母m表示。抛开B树的维护操作不谈，B树可以简单理解为一棵<strong>m叉搜索树</strong>。</p>
<blockquote>
<p>&emsp;&emsp;我们定义，一个树中，每个节点允许的子节点的最大数量，就称为这个数的阶，一般用字母m表示。例如：假设一棵5阶的B数，则B数上的每一个节点，最多只能有5个子节点。除此之外需要注意，B树的阶m &gt; 2。</p>
</blockquote>
<p>&emsp;&emsp;下面我们直接通过一张图来了解B树的结构：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="1.png" alt="" title="">
                </div>
                <div class="image-caption"></div>
            </figure>

<p>&emsp;&emsp;上面这张图就是一棵标准的B树，他的每一个节点中可能存有多个值（每个节点记录了值的个数，也就是上图中的红色数字），以及多个指向子节点的指针，而<strong>值的个数 = 指针的个数 - 1 = m - 1</strong>。比如说上图中，根节点存有一个值<code>50</code>（图中称为关键字），而根节点的左子节点存有两个值，即<code>10</code>和<code>30</code>。而由于根节点只有一个值，所以他有两个指向子节点的指针，从上图可以看出，这两个指针分别位于值的两边。我们之前说过，B树可以近似的认为是一棵m叉搜索树，所以上图中，根节点的左子树中的所有值都小于根节点的值<code>50</code>，而右边子树中所有节点的值大于根节点的值<code>50</code>。</p>
<blockquote>
<p>&emsp;&emsp;根节点只有一个值，以及两个子节点，和二叉树类似，所以以它举例不够典型，我们现在以根节点的左子节点再次举例。根节点的左子节点中存有两个值，即10和30，且他有3个指向子节点的指针。在每一个节点中，多个值是排好序的，比如上图中是从小到大排序，于是10在30的左边。对于10左边这个指针指向的子树，包含的值都小于10；而位于10和30之间的指针指向的子树，包含的值一定时10到30之间；而30右边的指针，指向的子树的子节点一定是大于30。</p>
</blockquote>
<p>&emsp;&emsp;我们现在以一个例子来说明B树查找的过程，假设上图中，我们想要搜索值<code>35</code>，于是需要经历以下步骤：</p>
<ol>
<li>用<code>35</code>与根节点中的值比较，根节点中只有一个<code>50</code>，<code>35&lt;50</code>，于是向根节点的左子节点搜索；</li>
<li>根节点的左子节点中的第一个值是<code>10</code>，<code>35&gt;10</code>，于是判断下一个值，下一个值为<code>30</code>，<code>35&gt;30</code>，继续判断下一个值，但是此节点中没有下一个值了，于是向<code>35</code>右边的这个指针指向的子节点查找，也就是第三个叶子节点；</li>
<li>到了叶子节点后，发现其中只有一个值，就是<code>35</code>，于是查找成功；</li>
</ol>
<p>&emsp;&emsp;以上就是在B树中查找一个值的过程。</p>
<br>

<h2 id="2-2-为什么需要B树"><a href="#2-2-为什么需要B树" class="headerlink" title="2.2 为什么需要B树?"></a>2.2 为什么需要B树?</h2><p>&emsp;&emsp;在B树的每一个节点中，都不止存储一个值，具体存储的值的个数依赖于B树的阶。而我们在查找一个值的过程中，需要对当前所在的节点包含的所有值进行一个遍历，以此来确定当前查找的值是否在当前节点中。这也就意味着，相比于二叉搜索树，平衡二叉树，红黑树等数据结构，B树查找一个值需要比较更多的次数。假设一棵B树的阶是<code>100</code>，那也就意味着在最坏情况下，我们在每一个访问到的节点中，都需要比较<code>100</code>次，而前面提到的三种数据结构比较的次数不会超过树的深度，也就是只需要少量的比较次数。既然B树相比较于它们需要比较更多的次数才能找到相应的值，那为什么还要B树呢？这取决于实际的应用场景。</p>
<p>&emsp;&emsp;说到B树，大部分首先想到的就是数据库的索引，<code>MySQL</code>中使用的索引主要为<code>BTree索引</code>（实际是B+树实现的，这个后面再谈）。从上面的B树结构我们可以看到，B树中使用大量的指针维护节点之间的关系，这也就意味着B树在物理存储上并不是连续的。单个节点中的数据是连续存储，但是多个节点之间一般都是单独存储，然后通过指针相互引用。在实际的存储中，<code>BTree索引</code>一般被存放在磁盘中，然后只有需要使用时，才将使用到的部分节点加载进内存，进行比较判断。</p>
<blockquote>
<p>&emsp;&emsp;为什么不一次性将BTree索引全部加载进内存？因为在实际生产中，索引往往需要维护百万甚至千万行数据，这就导致索引本身占据大量的内存，再加上我们使用的常常不止一个索引，再加上内存中需要运行其他程序，所以将索引一次性加载进内存是不现实的事情。只有当前需要使用的部分才被加载进内存，而不使用的部分则留在磁盘或者从内存中移除。</p>
</blockquote>
<p>&emsp;&emsp;而上面这种使用到才进行加载的方式有一个什么问题？我们每次需要查找树中的一个节点，都需要进行一次磁盘<code>IO</code>，将这个节点从磁盘中加载进内存。而对于B树或者说之前提到的平衡二叉树等数据结构，最多需要访问的节点的个数，实际上就是树的深度（想想搜索一个值的过程就能明白）。对于B树来说，他每一个节点可以存储多个值，而平衡二叉树等二叉结构，每一个节点只存储一个值，这也就意味着在值的个数相等的情况下，B树的深度小于二叉树的深度。这也就意味着以B树作为索引，可以进行更少次数的磁盘<code>IO</code>。</p>
<blockquote>
<p>&emsp;&emsp;对于一棵含有n个元素的树，二叉搜索树的深度在n-log2(n)之间，而平衡二叉树的深度是log2(n)，红黑树与平衡二叉树类似，平均深度也是log2(n)。然而，B树设计了一种高效简单的维护操作，使B树的深度维持在约log(ceil(m/2))(n)~logm(n)之间，<strong>大大降低树高</strong>（ceil是向上取整函数，例如5/2 = 3）。</p>
</blockquote>
<p>&emsp;&emsp;这里面临一个什么问题？<strong>磁盘的速度，相对于内存来说非常的缓慢，磁盘查找的速度比内存查找慢100000倍左右</strong>。也就是说，从磁盘中找到<code>1</code>个数据所花费的时间，可以从内存中查找<code>100000</code>个数据。这也就意味着我们在使用索引查找数据的过程中，时间主要是花费在了磁盘<code>IO</code>上，而不是数据的比较上。所以，我们希望尽可能少地进行磁盘<code>IO</code>。而B树作为索引，由于树的深度较小，相比于那些二叉树，可以进行更少的磁盘<code>IO</code>，这就是B树最大的优势。</p>
<p>&emsp;&emsp;二叉树中，一个节点一般只存储一个元素，而在将磁盘的数据加载进内存中时，实际上是按页进行加载的，页是每次从磁盘加载进内存的数据的最小单位，一般为<code>4K</code>。这也就意味着我们使用这些二叉树的数据结构时，加载一个节点所在的页进入内存时，这个页中有大量内存都是浪费的。而B树中每一个节点可以存储多个数据，于是我们可以通过修改B树的阶，让他的每一个节点大致占用一个页（4K）的大小，以此最大限度的减少B树的深度，提高内存利用率。</p>
<br>

<h2 id="2-3-B树存在的问题"><a href="#2-3-B树存在的问题" class="headerlink" title="2.3 B树存在的问题"></a>2.3 B树存在的问题</h2><p>&emsp;<strong>（1）难以存储具体数据</strong></p>
<p>&emsp;&emsp;我们上面在介绍B树的过程中，对于B树中存储的元素，都是用“值”这个字来说明，但是在上面那张图中可以看到，图中写的是关键字，这是因为我们在实际使用中，需要存储的是<code>key-value</code>型数据。比如说作为数据库索引，我们需要通过索引值进行查找，索引值就是<code>key</code>，但是我们真正需要的是索引值对应的数据行，也就是<code>value</code>。</p>
<p>&emsp;&emsp;有一个比较简单的解决方案，我们可以在B树的节点中直接存储<code>key</code>和<code>value</code>，这样在通过<code>key</code>找到元素是，可以直接取出<code>value</code>。但是，这会导致另外一个问题。我们上面说过，B树的一个节点，其大小一般被限制在一个磁盘页的大小（4K），如果我们在一个节点中既存<code>key</code>，又存<code>value</code>，就会导致一个节点中能够存储的元素数量减少，<code>value</code>越大，能够存储的元素就越少，于是树的深度就会增加，违背了我们使用B树减少磁盘<code>IO</code>的目的，所以这种方法并不可取。当然，其实也可以让<code>value</code>保存数据的地址，但是可能是需要综合考虑下面这个问题，所有没有这样做。</p>
<p>&emsp;<strong>（2）B树不适合用来处理范围查询</strong></p>
<p>&emsp;&emsp;在数据库中，进行范围查找的频率非常的高，比如查找员工工资在<code>1000-2000</code>中的全部员工这种类型的查询。但是，B树并不适合用来进行这种范围查找，因为在B树中，每一个节点都用来存储数据，它们之间并不是线性结构，不方便进行范围查询。想要在B树中进行范围查询，可以先找到范围的上界和下界，在通过DFS（或者BFS），遍历包含下界到上界中的所有节点，但这并不方便。</p>
<p>&emsp;&emsp;B+树正是针对以上两个问题，而对B树做了一些修改而得来。</p>
<br>

<h2 id="2-4-B-树"><a href="#2-4-B-树" class="headerlink" title="2.4 B+树"></a>2.4 B+树</h2><p>&emsp;&emsp;B+树相对于B树主要做了如下的修改：</p>
<ul>
<li>B+树中的每一个非叶子节点并不存储值<code>value</code>，只存储键<code>key</code>，而具体的<code>value</code>全部存放在子节点中，这也就意味着每次查找需要访问的节点数量都是固定的，都需要向下查找到子节点；</li>
<li>每一个子节点都有一个指向下一个子节点的指针，所有的子节点相互串联，组成一个线性的结构；</li>
<li>对于一个<code>m</code>阶的B+树，每一个节点最多只有m个子节点，同时存储<code>m</code>个<code>key</code>（对于<code>m</code>阶的B树，只有<code>m-1</code>个key）；</li>
<li>每一个子节点中最小（或最大）的<code>key</code>，也包含在父节点中（这个通过下面的例子理解）；</li>
</ul>
<p>&emsp;&emsp;下面我们通过一张图来看看B+树的结构：</p>
<figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="2.png" alt="" title="">
                </div>
                <div class="image-caption"></div>
            </figure>

<p>&emsp;&emsp;上图中，就是一棵B+树。根节点存储了<code>3</code>个<code>key</code>，<code>key</code>值分别是<code>5，28，65</code>，且是按照从小到达的顺序存储。同时根节点包含<code>3</code>个指针，指向自己的<code>3</code>个子节点。第一个子节点中最小的<code>key</code>是<code>5</code>，就是根节点中最小的<code>key</code>，而这个节点中所有的<code>key</code>，大小都是在根节点的第一个<code>key（5）</code>到第二个<code>key（28）</code>之间（不包含<code>28</code>）；第二个子节点中最小的<code>key</code>是<code>28</code>，也就是根节点中的第二个<code>key</code>，在这个子节点中所有的<code>key</code>，大小都在根节点第二个<code>key（28）</code>到第三个<code>key（65）</code>之间；第三个子节点同理，它包含根节点的第三个<code>key（65）</code>，同时其中所有的<code>key</code>都<code>&gt;=65</code>。再往下的子节点也是同理。</p>
<p>&emsp;&emsp;而根据上图我们可以看到，在最下层的叶子节点中，存储了全部的<code>key</code>值（尽管有些<code>key</code>已经在上层节点出现过），同时不仅存储了<code>key</code>值，还存储了这些<code>key</code>值对应的<code>value</code>。除此之外，每一个叶子节点都包含一个指针，指向下一个叶子节点。这些叶子节点相互串联，组成了一个<code>key</code>值从小到大排好序的线性结构。</p>
<p>&emsp;&emsp;这样处理有什么好处呢？好处就是我们在树中存储了<code>value</code>，但是由于<code>value</code>存储在叶子节点中，所以对于作为索引的非叶子节点来说，并没有增加它们的大小，从而并没有导致树的高度增加。除此之外，由于<code>value</code>都存储在叶子节点中，并且叶子节点相互串联，所以非常方便进行范围查询。比如说上图，我们要查找<code>key</code>为<code>26-60</code>对应的数据，那我们首先查找<code>26</code>所在的叶子节点，发现它在第三个叶子节点，于是我们将第三个叶子节点读入内存，然后发现并不包含全部数据，于是通过指针找到第四个叶子节点，将第四个叶子节点读入内存，还不包含全部，于是将第五个叶子节点也读入，这时就包含全部数据了。</p>
<br>

<h2 id="2-5-InnoDB和MyISAM中索引的实现"><a href="#2-5-InnoDB和MyISAM中索引的实现" class="headerlink" title="2.5 InnoDB和MyISAM中索引的实现"></a>2.5 InnoDB和MyISAM中索引的实现</h2><p>&emsp;&emsp;在<code>MySQL5.1</code>之前，<code>MySQL</code>的默认存储引擎是<code>MyISAM</code>，而在这之后改为了<code>InnoDB</code>。这两个存储引擎中，都使用了<code>B+Tree</code>实现索引，但是实现的方式有所区别。</p>
<p>&emsp;<strong>（1）InnoDB中的聚簇索引</strong></p>
<p>&emsp;&emsp;什么是聚簇索引，就是指索引与数据库表中的数据存储在一起。<code>InnoDB</code>使用B+树实现聚簇索引，而数据库表中的数据行，实际上就是存储在B+树的叶子节点中，我们上面说的B+树中的<code>key-value</code>，其中的<code>value</code>指的就是具体的一行数据，我们在叶子节点中找到了<code>key</code>，实际上也就得到了key对应的那一行数据。所以严格来讲，聚簇索引不单单是索引，更是数据的一种存储结构。</p>
<p>&emsp;&emsp;<code>InnoDB</code>使用表的主键作为<code>key</code>，建立聚簇索引，如果表没有主键，将选择一个唯一的非空索引替代，若也没有，将隐式的定义一个主键用来建立。</p>
<p>&emsp;<strong>（2）MyISAM的非聚簇索引</strong></p>
<p>&emsp;&emsp;在<code>MyISAM</code>中，并不使用聚簇索引，也就是说<code>MyISAM</code>中通过B+树实现的索引，并不包含表中具体的数据行，子节点中的<code>value</code>，存储的是这一行数据的地址，也就是说数据和索引分开存储。</p>
<br>

<h1 id="三、总结"><a href="#三、总结" class="headerlink" title="三、总结"></a>三、总结</h1><p>&emsp;&emsp;在<code>MySQL</code>的实际应用中，<code>BTree索引</code>都是通过B+树建立的，而不是B树。而在<code>InnoDB</code>中，使用的是聚簇索引，在B+树的叶子节点中直接存储表中的数据行；而<code>MyISAM</code>没有使用聚簇索引，B+树的叶子节点中，存放的是数据行的地址。</p>
<br>

<h1 id="四、参考"><a href="#四、参考" class="headerlink" title="四、参考"></a>四、参考</h1><ul>
<li><a href="https://mp.weixin.qq.com/s/_lNt8WtePf7lKaLsQzawxQ" target="_blank" rel="noopener">https://mp.weixin.qq.com/s/_lNt8WtePf7lKaLsQzawxQ</a></li>
<li><a href="https://mp.weixin.qq.com/s/HNN1CWmeXMOKtOe69lLJgQ" target="_blank" rel="noopener">https://mp.weixin.qq.com/s/HNN1CWmeXMOKtOe69lLJgQ</a></li>
</ul>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2020-04-04T19:32:07.869Z" itemprop="dateUpdated">2020-04-05 03:32:07</time>
</span><br>


        
        世界是个球，前方总有路！
        
    </div>
    
    <footer>
        <a href="http://tewuyiang.gitee.io/blog">
            <img src="/blog/img/avatar.jpg" alt="特务依昂">
            特务依昂
        </a>
    </footer>
</blockquote>

        


        <div class="post-footer">
            
	<ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/blog/tags/MySQL/" rel="tag">MySQL</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/&title=《MySQL中的索引为什么使用B+树实现》 — 博客主页&pic=http://tewuyiang.gitee.io/blog/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/&title=《MySQL中的索引为什么使用B+树实现》 — 博客主页&source=一个未来程序员的博客~~~" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《MySQL中的索引为什么使用B+树实现》 — 博客主页&url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/&via=http://tewuyiang.gitee.io/blog" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/blog/%E9%98%BB%E5%A1%9E%E9%98%9F%E5%88%97%E2%80%94%E2%80%94ArrayBlockingQueue%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">阻塞队列——ArrayBlockingQueue源码分析</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/blog/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F%EF%BC%882%EF%BC%89%E2%80%94%E2%80%94%E5%B7%A5%E5%8E%82%E6%A8%A1%E5%BC%8F%E8%AF%A6%E8%A7%A3/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">设计模式（2）——工厂模式详解</h4>
      </a>
    </div>
  
</nav>



    




















</article>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style='display:none'>
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style='display:none'>
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
                <span><a href="/blog/atom.xml" target="_blank" class="rss" title="rss"><i class="icon icon-lg icon-rss"></i></a></span>
            
            <span>博客内容遵循 <a rel="license noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>特务依昂 &copy; 2015 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/&title=《MySQL中的索引为什么使用B+树实现》 — 博客主页&pic=http://tewuyiang.gitee.io/blog/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/&title=《MySQL中的索引为什么使用B+树实现》 — 博客主页&source=一个未来程序员的博客~~~" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《MySQL中的索引为什么使用B+树实现》 — 博客主页&url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/&via=http://tewuyiang.gitee.io/blog" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://tewuyiang.gitee.io/blog/%E6%B5%85%E6%9E%90B%E6%A0%91%E3%80%81B-%E6%A0%91%E4%BB%A5%E5%8F%8AMySQL%E4%B8%AD%E7%9A%84%E4%BD%BF%E7%94%A8/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/blog/', SHARE: true, REWARD: false };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '人呢，怎么不见了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!欢迎回来!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
